<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="zh-Hans">
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-hemisu.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-hemisu.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-hemisu.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="hemisu">










<meta name="description" content="Just do...">
<meta name="keywords" content="web, 前端, 生活, 分享">
<meta property="og:type" content="website">
<meta property="og:title" content="何米酥`s Blog">
<meta property="og:url" content="http://www.hemisu.com/page/8/index.html">
<meta property="og:site_name" content="何米酥`s Blog">
<meta property="og:description" content="Just do...">
<meta property="og:locale" content="zh-Hans">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="何米酥`s Blog">
<meta name="twitter:description" content="Just do...">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":true,"scrollpercent":true,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://www.hemisu.com/page/8/">





  <title>何米酥`s Blog</title>
  








  <!-- Hotjar Tracking Code for www.hemisu.com -->
  <script>
      (function(h,o,t,j,a,r){
          h.hj=h.hj||function(){(h.hj.q=h.hj.q||[]).push(arguments)};
          h._hjSettings={hjid:1933736,hjsv:6};
          a=o.getElementsByTagName('head')[0];
          r=o.createElement('script');r.async=1;
          r.src=t+h._hjSettings.hjid+j+h._hjSettings.hjsv;
          a.appendChild(r);
      })(window,document,'https://static.hotjar.com/c/hotjar-','.js?sv=');
  </script>
</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left 
  page-home">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">何米酥`s Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle">EFE</p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br>
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br>
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br>
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            归档
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            
  <section id="posts" class="posts-expand">
    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/23/213/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/23/213/" itemprop="url">PAT A1064</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-23T18:40:08+00:00">
                2017-02-23
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:</p>
<p>The left subtree of a node contains only nodes with keys less than the node’s key.<br>The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.<br>Both the left and right subtrees must also be binary search trees.<br>A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right.</p>
<p>Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains a positive integer N (&lt;=1000). Then N distinct non-negative integer keys are given in the next line. All the numbers in a line are separated by a space and are no greater than 2000.</p>
<p>Output Specification:</p>
<p>For each test case, print in one line the level order traversal sequence of the corresponding complete binary search tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.</p>
<p>Sample Input:<br>10<br>1 2 3 4 5 6 7 8 9 0<br>Sample Output:<br>6 3 8 1 5 7 9 0 2 4</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 1010;</span><br><span class="line">//n为结点数，number用以存放结点权值，CBT用以存放完全二叉树</span><br><span class="line">//index从小到大枚举number数组</span><br><span class="line">int n, number[maxn], CBT[maxn], indexs = 0;</span><br><span class="line">void inOrder(int root)&#123;</span><br><span class="line">    if(root &gt; n) return;//空结点 返回</span><br><span class="line">    inOrder(2*root);//左子树</span><br><span class="line">    CBT[root] = number[indexs++];</span><br><span class="line">    inOrder(2*root +1);//右子树</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;number[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    sort(number, number + n);</span><br><span class="line">    inOrder(1);</span><br><span class="line">    for (int i = 1; i &lt;= n ; i++) &#123;</span><br><span class="line">        printf(&quot;%d&quot;, CBT[i]);</span><br><span class="line">        if(i &lt; n)   printf(&quot; &quot;);</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/23/212/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/23/212/" itemprop="url">PAT A1043</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-23T16:04:27+00:00">
                2017-02-23
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:</p>
<p>The left subtree of a node contains only nodes with keys less than the node’s key.<br>The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.<br>Both the left and right subtrees must also be binary search trees.<br>If we swap the left and right subtrees of every node, then the resulting tree is called the Mirror Image of a BST.</p>
<p>Now given a sequence of integer keys, you are supposed to tell if it is the preorder traversal sequence of a BST or the mirror image of a BST.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains a positive integer N (&lt;=1000). Then N integer keys are given in the next line. All the numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each test case, first print in a line “YES” if the sequence is the preorder traversal sequence of a BST or the mirror image of a BST, or “NO” if not. Then if the answer is “YES”, print in the next line the postorder traversal sequence of that tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.</p>
<p>Sample Input 1:<br>7<br>8 6 5 7 10 8 11<br>Sample Output 1:<br>YES<br>5 7 6 8 11 10 8<br>Sample Input 2:<br>7<br>8 10 11 8 6 7 5<br>Sample Output 2:<br>YES<br>11 8 10 7 5 6 8<br>Sample Input 3:<br>7<br>8 6 8 5 10 9 11<br>Sample Output 3:<br>NO<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">struct node&#123;</span><br><span class="line">    int data;</span><br><span class="line">    node *left, *right;</span><br><span class="line">&#125;;</span><br><span class="line">void insert(node* &amp;root, int data)&#123;</span><br><span class="line">    if (root == NULL) &#123;//到达空结点时，即为需要插入的位置</span><br><span class="line">        root = new node;</span><br><span class="line">        root-&gt;data = data;</span><br><span class="line">        root-&gt;left = root-&gt;right = NULL;</span><br><span class="line">        return;</span><br><span class="line">    &#125;</span><br><span class="line">    if (data &lt; root-&gt;data) &#123;</span><br><span class="line">        insert(root-&gt;left, data);</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        insert(root-&gt;right, data);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">void preOrder(node* root, vector&lt;int&gt;&amp;vi)&#123;//先序遍历，结果存在vi</span><br><span class="line">    if (root == NULL) return;</span><br><span class="line">    vi.push_back(root-&gt;data);</span><br><span class="line">    preOrder(root-&gt;left, vi);</span><br><span class="line">    preOrder(root-&gt;right, vi);</span><br><span class="line">&#125;</span><br><span class="line">void preOrderMirror(node* root, vector&lt;int&gt;&amp;vi)&#123;</span><br><span class="line">    if (root == NULL) return;</span><br><span class="line">    vi.push_back(root-&gt;data);</span><br><span class="line">    preOrderMirror(root-&gt;right, vi);</span><br><span class="line">    preOrderMirror(root-&gt;left, vi);</span><br><span class="line">&#125;</span><br><span class="line">void postOrder(node* root, vector&lt;int&gt;&amp;vi)&#123;</span><br><span class="line">    if (root == NULL) return;</span><br><span class="line">    postOrder(root-&gt;left, vi);</span><br><span class="line">    postOrder(root-&gt;right, vi);</span><br><span class="line">    vi.push_back(root-&gt;data);</span><br><span class="line">&#125;</span><br><span class="line">void postOrderMirror(node* root, vector&lt;int&gt;&amp;vi)&#123;</span><br><span class="line">    if (root == NULL) return;</span><br><span class="line">    postOrderMirror(root-&gt;right, vi);</span><br><span class="line">    postOrderMirror(root-&gt;left, vi);</span><br><span class="line">    vi.push_back(root-&gt;data);</span><br><span class="line">&#125;</span><br><span class="line">//origin存放初始序列</span><br><span class="line">//pre、post为先序、后序，preM、postM为镜像先序，后序</span><br><span class="line">vector&lt;int&gt; origin, pre, post, preM, postM;</span><br><span class="line">int main()&#123;</span><br><span class="line">    int n, data;</span><br><span class="line">    node* root = NULL;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;data);</span><br><span class="line">        origin.push_back(data);</span><br><span class="line">        insert(root, data);</span><br><span class="line">    &#125;</span><br><span class="line">    preOrder(root, pre);</span><br><span class="line">    preOrderMirror(root, preM);</span><br><span class="line">    postOrder(root, post);</span><br><span class="line">    postOrderMirror(root, postM);</span><br><span class="line">    if (origin == pre) &#123;</span><br><span class="line">        printf(&quot;YES\n&quot;);</span><br><span class="line">        for (int i = 0; i &lt; post.size(); i++) &#123;</span><br><span class="line">            printf(&quot;%d&quot;, post[i]);</span><br><span class="line">            if (i &lt; post.size() - 1) printf(&quot; &quot;);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;else if(origin == preM)&#123;</span><br><span class="line">        printf(&quot;YES\n&quot;);</span><br><span class="line">        for (int i = 0; i &lt; postM.size(); i++) &#123;</span><br><span class="line">            printf(&quot;%d&quot;, postM[i]);</span><br><span class="line">            if (i &lt; postM.size() - 1) printf(&quot; &quot;);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        printf(&quot;NO\n&quot;);</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/23/211/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/23/211/" itemprop="url">PAT A1004</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-23T15:03:50+00:00">
                2017-02-23
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.<br>Input</p>
<p>Each input file contains one test case. Each case starts with a line containing 0 &lt; N &lt; 100, the number of nodes in a tree, and M (&lt; N), the number of non-leaf nodes. Then M lines follow, each in the format:</p>
<p>ID K ID[1] ID[2] … ID[K]<br>where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID’s of its children. For the sake of simplicity, let us fix the root ID to be 01.<br>Output</p>
<p>For each test case, you are supposed to count those family members who have no child for every seniority level starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.</p>
<p>The sample case represents a tree with only 2 nodes, where 01 is the root and 02 is its only child. Hence on the root 01 level, there is 0 leaf node; and on the next level, there is 1 leaf node. Then we should output “0 1” in a line.</p>
<p>Sample Input<br>2 1<br>01 1 02<br>Sample Output<br>0 1<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 110;</span><br><span class="line">int n, m, maxDepth = 0;</span><br><span class="line">int countleaf[maxn] = &#123;0&#125;;</span><br><span class="line">struct node&#123;</span><br><span class="line">    vector&lt;int&gt; child;</span><br><span class="line">&#125;Node[maxn];</span><br><span class="line">void DFS(int index, int depth)&#123;</span><br><span class="line">    maxDepth = max(maxDepth , depth);</span><br><span class="line">    if (Node[index].child.size() == 0) &#123;//叶子结点</span><br><span class="line">        countleaf[depth]++;</span><br><span class="line">        return;</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 0; i &lt; Node[index].child.size(); i++) &#123;</span><br><span class="line">        DFS(Node[index].child[i], depth + 1);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d%d&quot;, &amp;n, &amp;m);</span><br><span class="line">    for (int i = 0; i &lt; m ; i++) &#123;</span><br><span class="line">        int id, k;</span><br><span class="line">        scanf(&quot;%d%d&quot;, &amp;id, &amp;k);</span><br><span class="line">        for (int j = 0; j &lt; k; j++) &#123;</span><br><span class="line">            int child;</span><br><span class="line">            scanf(&quot;%d&quot;, &amp;child);</span><br><span class="line">            Node[id].child.push_back(child);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    DFS(1,0);</span><br><span class="line">    for (int i = 0; i &lt;= maxDepth; i++) &#123;</span><br><span class="line">        printf(&quot;%d&quot;, countleaf[i]);</span><br><span class="line">        if (i &lt; maxDepth) printf(&quot; &quot;);</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/23/210/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/23/210/" itemprop="url">PAT A1106</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-23T14:36:27+00:00">
                2017-02-23
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>A supply chain is a network of retailers（零售商）, distributors（经销商）, and suppliers（供应商）– everyone involved in moving a product from supplier to customer.</p>
<p>Starting from one root supplier, everyone on the chain buys products from one’s supplier in a price P and sell or distribute them in a price that is r% higher than P. Only the retailers will face the customers. It is assumed that each member in the supply chain has exactly one supplier except the root supplier, and there is no supply cycle.</p>
<p>Now given a supply chain, you are supposed to tell the lowest price a customer can expect from some retailers.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, The first line contains three positive numbers: N (&lt;=105), the total number of the members in the supply chain (and hence their ID’s are numbered from 0 to N-1, and the root supplier’s ID is 0); P, the price given by the root supplier; and r, the percentage rate of price increment for each distributor or retailer. Then N lines follow, each describes a distributor or retailer in the following format:</p>
<p>Ki ID[1] ID[2] … ID[Ki]</p>
<p>where in the i-th line, Ki is the total number of distributors or retailers who receive products from supplier i, and is then followed by the ID’s of these distributors or retailers. Kj being 0 means that the j-th member is a retailer. All the numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each test case, print in one line the lowest price we can expect from some retailers, accurate up to 4 decimal places, and the number of retailers that sell at the lowest price. There must be one space between the two numbers. It is guaranteed that the all the prices will not exceed 1010.</p>
<p>Sample Input:<br>10 1.80 1.00<br>3 2 3 5<br>1 9<br>1 4<br>1 7<br>0<br>2 6 1<br>1 8<br>0<br>0<br>0<br>Sample Output:<br>1.8362 2<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 100010;</span><br><span class="line">int n, minDepth = maxn,minDepthCount = 0;</span><br><span class="line">double p, r;</span><br><span class="line">struct node&#123;</span><br><span class="line">    vector&lt;int&gt; child;</span><br><span class="line">&#125;Node[maxn];</span><br><span class="line">void DFS(int index, int depth)&#123;</span><br><span class="line">    if (Node[index].child.size() == 0) &#123;//叶子结点</span><br><span class="line">        if (depth &lt; minDepth) &#123;</span><br><span class="line">            minDepth = depth;</span><br><span class="line">            minDepthCount = 1;</span><br><span class="line">        &#125;else if(depth == minDepth)&#123;</span><br><span class="line">            minDepthCount++;</span><br><span class="line">        &#125;</span><br><span class="line">        return;</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 0; i &lt; Node[index].child.size(); i++) &#123;</span><br><span class="line">        DFS(Node[index].child[i], depth + 1);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d%lf%lf&quot;, &amp;n, &amp;p, &amp;r);</span><br><span class="line">    r /= 100;</span><br><span class="line">    for (int i = 0; i &lt; n ; i++) &#123;</span><br><span class="line">        int k;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;k);</span><br><span class="line">        for (int j = 0; j &lt; k; j++) &#123;</span><br><span class="line">            int child;</span><br><span class="line">            scanf(&quot;%d&quot;, &amp;child);</span><br><span class="line">            Node[i].child.push_back(child);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    DFS(0, 0);</span><br><span class="line">    printf(&quot;%.4f %d&quot;, p * pow(1 + r, minDepth), minDepthCount);</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/23/209/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/23/209/" itemprop="url">PAT A1094</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-23T14:31:17+00:00">
                2017-02-23
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>A family hierarchy is usually presented by a pedigree tree where all the nodes on the same level belong to the same generation. Your task is to find the generation with the largest population.</p>
<p><strong>Input Specification:</strong></p>
<p>Each input file contains one test case. Each case starts with two positive integers N (&lt;100) which is the total number of family members in the tree (and hence assume that all the members are numbered from 01 to N), and M (&lt;N) which is the number of family members who have children. Then M lines follow, each contains the information of a family member in the following format:</p>
<p>ID K ID[1] ID[2] … ID[K]</p>
<p>where ID is a two-digit number representing a family member, K (&gt;0) is the number of his/her children, followed by a sequence of two-digit ID’s of his/her children. For the sake of simplicity, let us fix the root ID to be 01. All the numbers in a line are separated by a space.</p>
<p><strong>Output Specification:</strong></p>
<p>For each test case, print in one line the largest population number and the level of the corresponding generation. It is assumed that such a generation is unique, and the root level is defined to be 1.</p>
<p><strong>Sample Input:</strong><br>23 13<br>21 1 23<br>01 4 03 02 04 05<br>03 3 06 07 08<br>06 2 12 13<br>13 1 21<br>08 2 15 16<br>02 2 09 10<br>11 2 19 20<br>17 1 22<br>05 1 11<br>07 1 14<br>09 1 17<br>10 1 18<br><strong>Sample Output:</strong><br>9 4</p>
<p>下面写了DFS和BFS两种做法，选择一项即可<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 110;</span><br><span class="line">int n, m;</span><br><span class="line">struct node&#123;</span><br><span class="line">    vector&lt;int&gt; child;</span><br><span class="line">    int level;</span><br><span class="line">&#125;Node[maxn];</span><br><span class="line">int hashTable[maxn] = &#123;0&#125;;</span><br><span class="line">void BFS(int root)&#123;</span><br><span class="line">    queue&lt;int&gt; q;</span><br><span class="line">    Node[root].level = 1;</span><br><span class="line">    q.push(root);</span><br><span class="line">    while (!q.empty()) &#123;</span><br><span class="line">        int now = q.front();</span><br><span class="line">        q.pop();</span><br><span class="line">        hashTable[Node[now].level]++;</span><br><span class="line">        for (int i = 0; i &lt; Node[now].child.size(); i++) &#123;</span><br><span class="line">            q.push(Node[now].child[i]);</span><br><span class="line">            Node[Node[now].child[i]].level = Node[now].level + 1;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">void DFS(int index, int depth)&#123;</span><br><span class="line">    hashTable[depth]++;</span><br><span class="line">    for (int j = 0; j &lt; Node[index].child.size(); j++) &#123;</span><br><span class="line">        DFS(Node[index].child[j], depth + 1);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d %d&quot;, &amp;n, &amp;m);</span><br><span class="line">    for (int i = 0 ; i &lt; m; i++) &#123;</span><br><span class="line">        int id, k;</span><br><span class="line">        scanf(&quot;%d%d&quot;, &amp;id, &amp;k);</span><br><span class="line">        for (int j = 0; j &lt; k; j++) &#123;</span><br><span class="line">            int child;</span><br><span class="line">            scanf(&quot;%d&quot;, &amp;child);</span><br><span class="line">            Node[id].child.push_back(child);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">//    BFS(1);</span><br><span class="line">    DFS(1, 1);</span><br><span class="line">    int maxk, maxnum = 0;</span><br><span class="line">    for (int i = 0; i &lt; maxn; i++) &#123;</span><br><span class="line">        if (hashTable[i] &gt; maxnum) &#123;</span><br><span class="line">            maxnum = hashTable[i];</span><br><span class="line">            maxk = i;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    printf(&quot;%d %d&quot;, maxnum, maxk);</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/23/208/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/23/208/" itemprop="url">PAT A1090</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-23T13:32:52+00:00">
                2017-02-23
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>A supply chain is a network of retailers（零售商）, distributors（经销商）, and suppliers（供应商）– everyone involved in moving a product from supplier to customer.</p>
<p>Starting from one root supplier, everyone on the chain buys products from one’s supplier in a price P and sell or distribute them in a price that is r% higher than P. It is assumed that each member in the supply chain has exactly one supplier except the root supplier, and there is no supply cycle.</p>
<p>Now given a supply chain, you are supposed to tell the highest price we can expect from some retailers.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, The first line contains three positive numbers: N (&lt;=105), the total number of the members in the supply chain (and hence they are numbered from 0 to N-1); P, the price given by the root supplier; and r, the percentage rate of price increment for each distributor or retailer. Then the next line contains N numbers, each number Si is the index of the supplier for the i-th member. Sroot for the root supplier is defined to be -1. All the numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each test case, print in one line the highest price we can expect from some retailers, accurate up to 2 decimal places, and the number of retailers that sell at the highest price. There must be one space between the two numbers. It is guaranteed that the price will not exceed 1010.</p>
<p>Sample Input:<br>9 1.80 1.00<br>1 5 4 4 -1 4 5 3 6<br>Sample Output:<br>1.85 2</p>
<p>与<a href="http://blog.hemisu.com/archives/206/" target="_blank" rel="noopener">1079</a>有点相似<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 100010;</span><br><span class="line">struct node &#123;</span><br><span class="line">    vector&lt;int&gt; child;//指针域</span><br><span class="line">    int level;//层数</span><br><span class="line">&#125;Node[maxn];</span><br><span class="line">int n;//总结点</span><br><span class="line">double p, r, maxPrice;</span><br><span class="line">int countMaxPrice;</span><br><span class="line">void DFS(int index, int depth)&#123;</span><br><span class="line">    if (Node[index].child.size() == 0) &#123;//叶节点</span><br><span class="line">        double price = p * pow(1 + r, depth);</span><br><span class="line">        if (price &gt; maxPrice) &#123;</span><br><span class="line">            countMaxPrice = 1;</span><br><span class="line">            maxPrice = price;</span><br><span class="line">        &#125;else if(price == maxPrice)&#123;</span><br><span class="line">            countMaxPrice++;</span><br><span class="line">        &#125;else &#123;</span><br><span class="line">            return;</span><br><span class="line">        &#125;</span><br><span class="line">        return;</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 0; i &lt; Node[index].child.size(); i++) &#123;</span><br><span class="line">        DFS(Node[index].child[i], depth + 1);</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">&#125;</span><br><span class="line">int findRoot()&#123;</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        if (Node[i].child[0] == -1) &#123;</span><br><span class="line">            return i;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return -1;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d%lf%lf&quot;, &amp;n, &amp;p, &amp;r);</span><br><span class="line">    r /= 100;</span><br><span class="line">    int root;</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        int cld;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;cld);</span><br><span class="line">        if (cld == -1)&#123;</span><br><span class="line">            root = i;</span><br><span class="line">            continue;</span><br><span class="line">        &#125;</span><br><span class="line">        Node[cld].child.push_back(i);</span><br><span class="line">    &#125;</span><br><span class="line">    DFS(root, 0);</span><br><span class="line">    printf(&quot;%.2f %d&quot;, maxPrice, countMaxPrice);</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/23/206/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/23/206/" itemprop="url">PAT A1079</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-23T10:25:00+00:00">
                2017-02-23
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>A supply chain is a network of retailers（零售商）, distributors（经销商）, and suppliers（供应商）– everyone involved in moving a product from supplier to customer.</p>
<p>Starting from one root supplier, everyone on the chain buys products from one’s supplier in a price P and sell or distribute them in a price that is r% higher than P. Only the retailers will face the customers. It is assumed that each member in the supply chain has exactly one supplier except the root supplier, and there is no supply cycle.</p>
<p>Now given a supply chain, you are supposed to tell the total sales from all the retailers.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains three positive numbers: N (&lt;=105), the total number of the members in the supply chain (and hence their ID’s are numbered from 0 to N-1, and the root supplier’s ID is 0); P, the unit price given by the root supplier; and r, the percentage rate of price increment for each distributor or retailer. Then N lines follow, each describes a distributor or retailer in the following format:</p>
<p>Ki ID[1] ID[2] … ID[Ki]</p>
<p>where in the i-th line, Ki is the total number of distributors or retailers who receive products from supplier i, and is then followed by the ID’s of these distributors or retailers. Kj being 0 means that the j-th member is a retailer, then instead the total amount of the product will be given after Kj. All the numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each test case, print in one line the total sales we can expect from all the retailers, accurate up to 1 decimal place. It is guaranteed that the number will not exceed 1010.</p>
<p>Sample Input:<br>10 1.80 1.00<br>3 2 3 5<br>1 9<br>1 4<br>1 7<br>0 7<br>2 6 1<br>1 8<br>0 9<br>0 4<br>0 3<br>Sample Output:<br>42.4<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 100010;</span><br><span class="line">struct node &#123;</span><br><span class="line">    int weight;//数据域</span><br><span class="line">    vector&lt;int&gt; child;//指针域</span><br><span class="line">    int level;//层数</span><br><span class="line">&#125;Node[maxn];</span><br><span class="line">int n;//总结点</span><br><span class="line">double p, r;</span><br><span class="line"></span><br><span class="line">double levelOrder(int root)&#123;</span><br><span class="line">    double ans = 0.0;</span><br><span class="line">    queue&lt;int&gt; q;//队列初始化</span><br><span class="line">    q.push(root);//入队</span><br><span class="line">    Node[root].level = 0;</span><br><span class="line">    while (!q.empty()) &#123;</span><br><span class="line">        int now = q.front();</span><br><span class="line">        q.pop();</span><br><span class="line">        int level = Node[now].level;</span><br><span class="line">        if (Node[now].weight) &#123;</span><br><span class="line">            ans += p * pow((1+ r/100.0), level) * Node[now].weight;</span><br><span class="line">        &#125;</span><br><span class="line">        for (int i = 0; i &lt; Node[now].child.size(); i++) &#123;</span><br><span class="line">            q.push(Node[now].child[i]);</span><br><span class="line">            Node[Node[now].child[i]].level = Node[now].level + 1;//层数加1</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return ans;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d%lf%lf&quot;, &amp;n, &amp;p, &amp;r);</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        int k;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;k);//供应人数</span><br><span class="line">        for (int j = 0; j &lt; k; j++) &#123;</span><br><span class="line">            int id;</span><br><span class="line">            scanf(&quot;%d&quot;, &amp;id);</span><br><span class="line">            Node[i].child.push_back(id);//有供应商就添加</span><br><span class="line">        &#125;</span><br><span class="line">        if (k == 0) &#123;//是零售</span><br><span class="line">            scanf(&quot;%d&quot;, &amp;Node[i].weight);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    printf(&quot;%.1f&quot;,levelOrder(0));</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>书上答案dfs：<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 100010;</span><br><span class="line">struct node &#123;</span><br><span class="line">    int weight;//数据域</span><br><span class="line">    vector&lt;int&gt; child;//指针域</span><br><span class="line">    int level;//层数</span><br><span class="line">&#125;Node[maxn];</span><br><span class="line">int n;//总结点</span><br><span class="line">double p, r, ans = 0;</span><br><span class="line">void DFS(int index, int depth)&#123;</span><br><span class="line">    if (Node[index].child.size() == 0) &#123;//叶节点</span><br><span class="line">        ans += Node[index].weight * pow(1 + r, depth);//累加叶节点货物的价格</span><br><span class="line">        return;</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 0; i &lt; Node[index].child.size(); i++) &#123;</span><br><span class="line">        DFS(Node[index].child[i], depth + 1);</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d%lf%lf&quot;, &amp;n, &amp;p, &amp;r);</span><br><span class="line">    r /= 100;</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        int k;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;k);//供应人数</span><br><span class="line">        for (int j = 0; j &lt; k; j++) &#123;</span><br><span class="line">            int id;</span><br><span class="line">            scanf(&quot;%d&quot;, &amp;id);</span><br><span class="line">            Node[i].child.push_back(id);//有供应商就添加</span><br><span class="line">        &#125;</span><br><span class="line">        if (k == 0) &#123;//是零售</span><br><span class="line">            scanf(&quot;%d&quot;, &amp;Node[i].weight);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    DFS(0, 0);</span><br><span class="line">    printf(&quot;%.1f&quot;,p * ans);</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/22/205/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/22/205/" itemprop="url">PAT A1053</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-22T19:56:51+00:00">
                2017-02-22
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Given a non-empty tree with root R, and with weight Wi assigned to each tree node Ti. The weight of a path from R to L is defined to be the sum of the weights of all the nodes along the path from R to any leaf node L.</p>
<p>Now given any weighted tree, you are supposed to find all the paths with their weights equal to a given number. For example, let’s consider the tree showed in Figure 1: for each node, the upper number is the node ID which is a two-digit number, and the lower number is the weight of that node. Suppose that the given number is 24, then there exists 4 different paths which have the same given weight: {10 5 2 7}, {10 4 10}, {10 3 3 6 2} and {10 3 3 6 2}, which correspond to the red edges in Figure 1.</p>
<p><img src="https://www.patest.cn/upload/5b_mj58f84v11w.jpg" alt="请输入图片描述"><br>Figure 1<br><strong>Input Specification:</strong></p>
<p>Each input file contains one test case. Each case starts with a line containing 0 &lt; N &lt;= 100, the number of nodes in a tree, M (&lt; N), the number of non-leaf nodes, and 0 &lt; S &lt; 230, the given weight number. The next line contains N positive numbers where Wi (&lt;1000) corresponds to the tree node Ti. Then M lines follow, each in the format:</p>
<p>ID K ID<a href="https://www.patest.cn/upload/5b_mj58f84v11w.jpg" target="_blank" rel="noopener">1</a> ID[2] … ID[K]<br>where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID’s of its children. For the sake of simplicity, let us fix the root ID to be 00.</p>
<p><strong>Output Specification:</strong></p>
<p>For each test case, print all the paths with weight S in non-increasing order. Each path occupies a line with printed weights from the root to the leaf in order. All the numbers must be separated by a space with no extra space at the end of the line.</p>
<p>Note: sequence {A1, A2, …, An} is said to be greater than sequence {B1, B2, …, Bm} if there exists 1 &lt;= k &lt; min{n, m} such that Ai = Bi for i=1, … k, and Ak+1 &gt; Bk+1.</p>
<p><strong>Sample Input:</strong><br>20 9 24<br>10 2 4 3 5 10 2 18 9 7 2 2 1 3 12 1 8 6 2 2<br>00 4 01 02 03 04<br>02 1 05<br>04 2 06 07<br>03 3 11 12 13<br>06 1 09<br>07 2 08 10<br>16 1 15<br>13 3 14 16 17<br>17 2 18 19<br><strong>Sample Output:</strong><br>10 5 2 7<br>10 4 10<br>10 3 3 6 2<br>10 3 3 6 2</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">//#include &quot;stack&quot;</span><br><span class="line">//#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 110;</span><br><span class="line">struct node &#123;</span><br><span class="line">    int weight;//数据域</span><br><span class="line">    vector&lt;int&gt; child;//指针域</span><br><span class="line">&#125;Node[maxn];</span><br><span class="line">bool cmp(int a, int b)&#123;</span><br><span class="line">    return Node[a].weight &gt; Node[b].weight;</span><br><span class="line">&#125;</span><br><span class="line">int n, m, S;//结点数、边数、给定的和</span><br><span class="line">int path[maxn];//记录路径</span><br><span class="line">//当前访问结点为index, nowNode为当前路径path上的结点个数</span><br><span class="line">//sum为当前的结点weight和</span><br><span class="line">void DFS(int index, int numNode, int sum)&#123;</span><br><span class="line">    if (sum &gt; S) return;//当前和不等于S</span><br><span class="line">    if (sum == S) &#123;//当前和等于S</span><br><span class="line">        if (Node[index].child.size()) return;//当前和等于S但不是叶子结点</span><br><span class="line">        for (int i = 0; i &lt; numNode; i++) &#123;</span><br><span class="line">            printf(&quot;%d&quot;, Node[path[i]].weight);</span><br><span class="line">            if (i &lt; numNode - 1) printf(&quot; &quot;);</span><br><span class="line">            else printf(&quot;\n&quot;);</span><br><span class="line">        &#125;</span><br><span class="line">        return;</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 0; i &lt; Node[index].child.size(); i++) &#123;//枚举孩子结点</span><br><span class="line">        int child = Node[index].child[i];</span><br><span class="line">        path[numNode] = child;//将结点child添加到路径path末尾</span><br><span class="line">        DFS(child, numNode + 1, sum + Node[child].weight);//递归下一层</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d%d%d&quot;, &amp;n, &amp;m, &amp;S);</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;Node[i].weight);</span><br><span class="line">    &#125;</span><br><span class="line">    int id, k, child;</span><br><span class="line">    for (int i = 0; i &lt; m; i++) &#123;</span><br><span class="line">        scanf(&quot;%d%d&quot;, &amp;id, &amp;k);</span><br><span class="line">        for (int j = 0; j &lt; k; j++) &#123;</span><br><span class="line">            scanf(&quot;%d&quot;, &amp;child);</span><br><span class="line">            Node[id].child.push_back(child);//child为结点id的孩子</span><br><span class="line">        &#125;</span><br><span class="line">        sort(Node[id].child.begin(), Node[id].child.end(), cmp);</span><br><span class="line">    &#125;</span><br><span class="line">    path[0] = 0;//路径设置第一个结点为0号结点</span><br><span class="line">    DFS(0, 1, Node[0].weight);//DFS求解</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/22/203/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/22/203/" itemprop="url">PAT A1102</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-22T18:10:50+00:00">
                2017-02-22
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>The following is from Max Howell @twitter:</p>
<p>Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.</p>
<p>Now it’s your turn to prove that YOU CAN invert a binary tree!</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line gives a positive integer N (&lt;=10) which is the total number of nodes in the tree – and hence the nodes are numbered from 0 to N-1. Then N lines follow, each corresponds to a node from 0 to N-1, and gives the indices of the left and right children of the node. If the child does not exist, a “-“ will be put at the position. Any pair of children are separated by a space.</p>
<p>Output Specification:</p>
<p>For each test case, print in the first line the level-order, and then in the second line the in-order traversal sequences of the inverted tree. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.</p>
<p>Sample Input:<br>8<br>1 -</p>
<ul>
<li>-<br>0 -<br>2 7</li>
<li>-</li>
<li>-<br>5 -<br>4 6<br>Sample Output:<br>3 7 2 6 4 0 5 1<br>6 5 7 4 3 2 0 1<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">#include &quot;stack&quot;</span><br><span class="line">#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 30;</span><br><span class="line">struct node&#123;</span><br><span class="line">    int lchild;</span><br><span class="line">    int rchild;</span><br><span class="line">&#125;Node[maxn];</span><br><span class="line">bool notRoot[maxn] = &#123;false&#125;;//记录是否不是根结点，初始均是根结点</span><br><span class="line">int n, num = 0;//n为结点个数，num为当前已经输出的结点个数</span><br><span class="line">//print函数输出结点id的编号</span><br><span class="line">void print(int id)&#123;</span><br><span class="line">    printf(&quot;%d&quot;, id);//输出id</span><br><span class="line">    num++;//已经输出的结点个数+1</span><br><span class="line">    if (num &lt; n) &#123;</span><br><span class="line">        printf(&quot; &quot;);</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        printf(&quot;\n&quot;);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">//中序遍历</span><br><span class="line">void inOrder(int root)&#123;</span><br><span class="line">    if (root == -1) &#123;</span><br><span class="line">        return;</span><br><span class="line">    &#125;</span><br><span class="line">    inOrder(Node[root].lchild);</span><br><span class="line">    print(root);</span><br><span class="line">    inOrder(Node[root].rchild);</span><br><span class="line">&#125;</span><br><span class="line">//层次遍历</span><br><span class="line">void BFS(int root)&#123;</span><br><span class="line">    queue&lt;int&gt; Q;</span><br><span class="line">    Q.push(root);</span><br><span class="line">    while (!Q.empty()) &#123;</span><br><span class="line">        int now = Q.front();</span><br><span class="line">        Q.pop();</span><br><span class="line">        print(now);</span><br><span class="line">        if (Node[now].lchild != -1) Q.push(Node[now].lchild);</span><br><span class="line">        if (Node[now].rchild != -1) Q.push(Node[now].rchild);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">//后序遍历 用于反转二叉树</span><br><span class="line">void postOrder(int root)&#123;</span><br><span class="line">    if (root == -1) &#123;</span><br><span class="line">        return;</span><br><span class="line">    &#125;</span><br><span class="line">    postOrder(Node[root].lchild);</span><br><span class="line">    postOrder(Node[root].rchild);</span><br><span class="line">    swap(Node[root].lchild, Node[root].rchild);//交换左右孩子结点</span><br><span class="line">&#125;</span><br><span class="line">//将输入的字符转换为-1或者结点编号</span><br><span class="line">int strToNum(char c)&#123;</span><br><span class="line">    if (c == &apos;-&apos;) &#123;</span><br><span class="line">        return -1;</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        notRoot[c - &apos;0&apos;] = true;//标记c不是根节点</span><br><span class="line">        return c - &apos;0&apos;;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">//寻找根节点</span><br><span class="line">int findRoot()&#123;</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        if (notRoot[i] == false) &#123;</span><br><span class="line">            return i;//是根节点，返回</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return -1;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    char lchild, rchild;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;n);//结点个数</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        scanf(&quot;%*c%c %c&quot;, &amp;lchild, &amp;rchild);//左右孩子结点</span><br><span class="line">        Node[i].lchild = strToNum(lchild);</span><br><span class="line">        Node[i].rchild = strToNum(rchild);</span><br><span class="line">    &#125;</span><br><span class="line">    int root = findRoot();</span><br><span class="line">    postOrder(root);//翻转二叉树</span><br><span class="line">    BFS(root);</span><br><span class="line">    num = 0;</span><br><span class="line">    inOrder(root);</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></li>
</ul>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/22/202/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/22/202/" itemprop="url">PAT A1086</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-22T16:38:31+00:00">
                2017-02-22
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.<br><img src="https://www.patest.cn/upload/bs_n9mde9jcnyj.jpg" alt="请输入图片描述"></p>
<p>Figure 1<br>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains a positive integer N (&lt;=30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: “Push X” where X is the index of the node being pushed onto the stack; or “Pop” meaning to pop one node from the stack.</p>
<p>Output Specification:</p>
<p>For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.</p>
<p>Sample Input:<br>6<br>Push 1<br>Push 2<br>Push 3<br>Pop<br>Pop<br>Push 4<br>Pop<br>Pop<br>Push 5<br>Push 6<br>Pop<br>Pop<br>Sample Output:<br>3 4 2 6 5 1</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">//#include &quot;map&quot;</span><br><span class="line">#include &quot;stack&quot;</span><br><span class="line">//#include &quot;queue&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 50;</span><br><span class="line">struct node&#123;</span><br><span class="line">    int data;</span><br><span class="line">    node* lchild;</span><br><span class="line">    node* rchild;</span><br><span class="line">&#125;;</span><br><span class="line">int pre[maxn], in[maxn], post[maxn];//先序，中序以及后序</span><br><span class="line">int n;//结点个数</span><br><span class="line"></span><br><span class="line">//当前二叉树的先序序列区间为[preL, preR],中序序列区间为[inL, inR]</span><br><span class="line">//create函数返回根节点</span><br><span class="line">node* create(int preL, int preR, int inL, int inR)&#123;</span><br><span class="line">    if (preL &gt; preR) return NULL;</span><br><span class="line">    node* root = new node;</span><br><span class="line">    root-&gt;data = pre[preL];</span><br><span class="line">    int k;</span><br><span class="line">    for (k = inL; k &lt;= inR; k++) &#123;</span><br><span class="line">        if (in[k] == pre[preL]) break;</span><br><span class="line">    &#125;</span><br><span class="line">    int numLeft = k - inL;</span><br><span class="line">    root-&gt;lchild = create(preL + 1, preL + numLeft, inL, k - 1);</span><br><span class="line">    root-&gt;rchild = create(preL + numLeft + 1, preR, k + 1, inR);</span><br><span class="line">    return root;</span><br><span class="line">&#125;</span><br><span class="line">int num = 0;//已输出的结点个数</span><br><span class="line">void postorder(node* root)&#123;</span><br><span class="line">    //后序遍历</span><br><span class="line">    if (root == NULL) &#123;</span><br><span class="line">        return;</span><br><span class="line">    &#125;</span><br><span class="line">    postorder(root-&gt;lchild);</span><br><span class="line">    postorder(root-&gt;rchild);</span><br><span class="line">    printf(&quot;%d&quot;, root-&gt;data);</span><br><span class="line">    num++;</span><br><span class="line">    if(num &lt; n) printf(&quot; &quot;);</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;n);</span><br><span class="line">    char str[5];</span><br><span class="line">    stack&lt;int&gt; st;</span><br><span class="line">    int x, preIndex = 0, inIndex = 0;//入栈元素、先序序列位置及中序序列位置</span><br><span class="line">    for (int i = 0; i &lt; 2 * n; i++) &#123;</span><br><span class="line">        scanf(&quot;%s&quot;, str);</span><br><span class="line">        if (strcmp(str, &quot;Push&quot;) == 0) &#123;//入栈</span><br><span class="line">            scanf(&quot;%d&quot;, &amp;x);</span><br><span class="line">            pre[preIndex++] = x;</span><br><span class="line">            st.push(x);</span><br><span class="line">        &#125;else&#123;</span><br><span class="line">            in[inIndex++] = st.top();</span><br><span class="line">            st.pop();</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    node* root = create(0, n-1, 0, n-1);</span><br><span class="line">    postorder(root);</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
  </section>

  
  <nav class="pagination">
    <a class="extend prev" rel="prev" href="/page/7/"><i class="fa fa-angle-left"></i></a><a class="page-number" href="/">1</a><span class="space">&hellip;</span><a class="page-number" href="/page/7/">7</a><span class="page-number current">8</span><a class="page-number" href="/page/9/">9</a><span class="space">&hellip;</span><a class="page-number" href="/page/21/">21</a><a class="extend next" rel="next" href="/page/9/"><i class="fa fa-angle-right"></i></a>
  </nav>



          </div>
          


          

        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      

      <section class="site-overview-wrap sidebar-panel sidebar-panel-active">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image" src="/images/avatar.jpg" alt="何米酥">
            
              <p class="site-author-name" itemprop="name">何米酥</p>
              <p class="site-description motion-element" itemprop="description">Just do...</p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">202</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">8</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">78</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a href="https://github.com/hemisu" target="_blank" title="GitHub">
                      
                        <i class="fa fa-fw fa-github"></i>GitHub</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="https://www.zhihu.com/people/hemisu" target="_blank" title="知乎">
                      
                        <i class="fa fa-fw fa-globe"></i>知乎</a>
                  </span>
                
            </div>
          

          
          

          
          

          

        </div>
      </section>

      

      
        <div class="back-to-top">
          <i class="fa fa-arrow-up"></i>
          
            <span id="scrollpercent"><span>0</span>%</span>
          
        </div>
      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; 2015 &mdash; <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">何米酥</span>

  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Gemini</a> v5.1.4</div>




        







        
      </div>
    </footer>

    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  

  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  





  

  

  

  
  

  

  

  

</body>
</html>
